1361B - Johnny and Grandmaster - CodeForces Solution

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1000000;
long long mod = 1000000007;

long long ksm(long long p, long long x) {
	long long res = 1;
	while(x) {
		if(x & 1) {
			res = (res * p) % mod;
		}
		p = (p * p) % mod;
		x >>= 1;
	}
	return res;
}

struct asd{
	int v, c;
}e[N];

int main() {
	int t, i, n, p, a[N];
	bool flag;
	int tar, k, l;
	long long res;
	for(cin >> t; t; t--) {
		cin >> n >> p;
		flag = true;
		l = 0;
		for(i = 0; i < n; i++) cin >> a[i];
		if(p == 1) {
			cout << n % 2 << endl;
			continue;
		}
		sort(a, a + n);
		tar = a[n - 1];
		for(i = n - 2; i > -1; i--) {
			k = a[i];
			while(l && k == e[l - 1].v && e[l - 1].c == p - 1) {
				l--;
				k++;
			}
			if(k == tar) {
				if(i == 0) {
					cout << 0 << endl;
					flag = false;
					l = 0;
					break;
				}
				i--;
				tar = a[i];
			} else if(l && k == e[l - 1].v) {
				e[l - 1].c++;
			} else {
				e[l].c = 1;
				e[l].v = k;
				l++;
			}
		}
		res = ksm(p, tar);
		for(i = 0; i < l; i++) {
			res -= e[i].c * ksm(p, e[i].v);
			res %= mod;
		}
		res = (res + mod) % mod;
		if(flag) cout << res << endl;
	}
	return 0;
}